import functools
from typing import List


class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        @functools.lru_cache(None)
        def dfs(x, y1, y2):
            if not 0 <= y1 < n or not 0 <= y2 < n:
                return 0
            if x == m:
                return 0

            if y1 == y2:
                ans = grid[x][y1]
            else:
                ans = grid[x][y1] + grid[x][y2]

            ans += max(
                dfs(x + 1, y1 - 1, y2 - 1),
                dfs(x + 1, y1 - 1, y2),
                dfs(x + 1, y1 - 1, y2 + 1),
                dfs(x + 1, y1, y2 - 1),
                dfs(x + 1, y1, y2),
                dfs(x + 1, y1, y2 + 1),
                dfs(x + 1, y1 + 1, y2 - 1),
                dfs(x + 1, y1 + 1, y2),
                dfs(x + 1, y1 + 1, y2 + 1),
            )

            return ans

        return dfs(0, 0, n - 1)


if __name__ == "__main__":
    # 24
    print(Solution().cherryPickup(grid=[[3, 1, 1], [2, 5, 1], [1, 5, 5], [2, 1, 1]]))

    # 28
    print(Solution().cherryPickup(grid=[[1, 0, 0, 0, 0, 0, 1],
                                        [2, 0, 0, 0, 0, 3, 0],
                                        [2, 0, 9, 0, 0, 0, 0],
                                        [0, 3, 0, 5, 4, 0, 0],
                                        [1, 0, 2, 3, 0, 0, 6]]))

    # 22
    print(Solution().cherryPickup(grid=[[1, 0, 0, 3], [0, 0, 0, 3], [0, 0, 3, 3], [9, 0, 3, 3]]))

    # 4
    print(Solution().cherryPickup(grid=[[1, 1], [1, 1]]))
